import collections


class Solution(object):
    def minimumHammingDistance(self, source, target, allowedSwaps):
        n = len(source)
        p = [i for i in range(n)]
        d = collections.defaultdict(list)
        def find(x):
            if x == p[x]:
                return x
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx > rooty:
                    p[rootx] = rooty
                else:
                    p[rooty] = rootx

        for u, v in allowedSwaps:
            union(u, v)

        for i in range(n):
            d[find(i)].append(i)
        ans = 0
        for key in d:
            nums1 = [source[index] for index in d[key]]
            nums2 = [target[index] for index in d[key]]
            m = len(nums1)
            c1 = collections.Counter(nums1)
            c2 = collections.Counter(nums2)
            t = 0
            for key in c1:
                t += min(c1[key], c2[key])
            ans += m - t
        return ans



